

print("给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标")
def twoSum(nums:list[int],target:int) -> list[int]:
    for i in range(0,len(nums)):
        for j in range(i+1,len(nums)):
            if nums[i]+nums[j] == target:
                return [i,j]
    return []

print("给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false")
def isPalindrome(x:int)->bool:
    return str(x) == str(x)[::-1]


print("编写一个函数来查找字符串数组中的最长公共前缀")
def longestCommonPrefix(strs:list[str]) ->str:
    strs.sort(key=lambda s:len(s))
    longest_prefix = ""
    for i in range(0,len(strs[0])):
        if len(set([s[i] for s in strs])) > 1:
            break
        longest_prefix = longest_prefix+strs[0][i]
    return longest_prefix

print("给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效")
def isValid(strs:str)->bool:
    for i in range(0,len(strs)//2):
        strs = strs.replace("()","").replace("{}","").replace("[]","")
    return len(strs) == 0

def isValid2(s:str) -> bool:
    stack = []
    temp_mapping = {")":"(","}":"{","]":"["}
    for ss in s:
        if ss in temp_mapping:
            if len(stack) ==0:
                return False
            elif stack.pop() != temp_mapping.get(ss):
                return False
        else:
            stack.append(ss)
    return len(stack) == 0


print("给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，"
      "返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数")
def removeDuplicates(nums:list[int]) -> int:
    nums2 = sorted(list(set(nums)))
    for i in range(0,len(nums2)):
        nums[i] = nums2[i]
    return len(nums2)

print("给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。"
      "元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量")
def removeElement(nums:list[int],val:int)->int:
    count = nums.count(val)
    for i in range(0,count):
        nums.remove(val)
    return len(nums)



print("给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。"
      "如果 needle 不是 haystack 的一部分，则返回  -1")
def strStr(haystack:str,needle:str) -> int:
    if needle in haystack:
        return haystack.index(needle)
    return -1

print("给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置")
def searchInsert(nums:list[int],target:int) ->int:
    if target in nums:
        return nums.index(target)
    nums.append(target)
    nums.sort()
    return nums.index(target)

print("给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度")
def lengthOfLastWord(strs:str) -> int:
    strs = "   fly me   to   the moon  "
    print(strs.split())
    print(strs.split()[-1])
    return len(strs.split()[-1])


print("给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。")
def plusOne(digits:list[int]) ->list[int]:
    digits = digits[::-1]
    for i in range(0,len(digits)):
        if digits[i] == 9 and i == len(digits) -1:
            digits[i] = 0
            digits.append(1)
        elif digits[i] ==9:
            digits[i] = 0
        else:
            digits[i] = digits[i]+1
            break
    return digits[::-1]

print("给你一个非负整数 x ，计算并返回 x 的 算术平方根"
      "由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去")
def mySqrt(x:int) -> int:
    if x ==0:
        return 0
    if x ==1:
        return 1
    for i in range(0,x):
        if i**2 == x:
            return i
        if i**2<x and (i+1)**2>x:
            return i

print("假设你正在爬楼梯。需要 n 阶你才能到达楼顶"
      "每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?")
def climbStairs(n:int) ->int:
    if n ==0 or n ==1:
        return 1
    return climbStairs(n-1)+climbStairs(n-2)

print("删除排序链表中的重复元素"
      "给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表")
class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next = next
def deleteDuplicates(head:ListNode) ->ListNode:
    if head is None:
        return None
    current = head
    while current.next:
        if current.val == current.next.val:
            current.next=current.next.next
            current=current.next
        else:
            current = current.next
    return head
node1=ListNode(val=1)
node2=ListNode(val=1)
node3=ListNode(val=2)
node1.next=node2
node2.next=node3
head_modified = deleteDuplicates(node1)
current = head_modified
while current:
    print(current.val)
    current=current.next
print("None")

print("合并两个有序数组，合并后同样非递减"
      "给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目")
def merge(nums1:list[int],m:int,nums2:list[int],n:int) -> None:
    nums1[m:]=nums2
    nums1.sort()

class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right

print("二叉树的中序遍历")
def inorderTraversal(root:TreeNode)->list[int]:
    temp = []
    def dfs(node):
        if node is None:
            return
        dfs(node.left)
        temp.append(node.val)
        dfs(node.right)
    dfs(root)
    return temp

class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val = val
        self.left=left
        self.right=right
print("二叉树的前序遍历")
def preorderTraversal(root:TreeNode)->list[int]:
    temp=[]
    def dfs(node):
        if node is None:
            return
        temp.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return temp


print("二叉树的后序遍历")
class TreeNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
def postorderTraversal(head:TreeNode)->list[int]:
    temp=[]
    def dfs(node:TreeNode):
        if node is None:
            return
        dfs(node.left)
        dfs(node.right)
        temp.append(node.val)
    dfs(head)
    return temp


print("给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同"
      "如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的")
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
def isSameTree(p:TreeNode,q:TreeNode)->bool:
    if p is None and q is None:
        return True
    elif p is None or q is None or p.val != q.val:
        return False
    return p.val==q.val and isSameTree(p.left,q.left) and isSameTree(p.right,q.right)
    # if p is None or q is None:
    #     return p==q
    # return p.val==q.val and isSameTree(p.left,q.left) and isSameTree(p.right,q.right)

print("给你一个二叉树的根节点 root ， 检查它是否轴对称")
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
def isSymmetric(root:TreeNode)->bool:
    def innerSymmetric(left:TreeNode,right:TreeNode):
        if left is None and right is None:
            return True
        elif left is None or right is None or left.val != right.val:
            return False
        return innerSymmetric(left.left,right.right) and innerSymmetric(left.right,right.left)
    if root is None:
        return False
    else:
        return innerSymmetric(left=root.left,right=root.right)

print("二叉树的最大深度")
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right

def maxDepth(root:TreeNode)->int:
    if root is None:
        return 0
    max_l=0
    max_r=0
    max_l=maxDepth(root.left)
    max_r=maxDepth(root.right)
    return max(max_l,max_r)+1

print("二叉树的最小深度")
def minDepth(root:TreeNode) ->int:
    if not root:
        return 0
    if root.left is None:
        return minDepth(root.right)+1
    if root.right is None:
        return min(root.left)+1

print("生成杨辉三角的前n行")
def generate(numRows:int) ->list[list[int]]:
    source_list = [[1]*(i+1) for i in range(0,numRows)]
    print(source_list)
    for i in range(2,numRows):
        for j in range(1,len(source_list[i])-1):
            source_list[i][j] = source_list[i-1][j-1]+source_list[i-1][j]
    print(source_list)
    return source_list
generate(5)


print("给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行")
def getRow(rowIndex:int) -> list[int]:
    if rowIndex ==0:
        return [1]
    source_list = [[1]*(r+1) for r in range(0,rowIndex+1)]
    print(source_list)
    for i in range(2,rowIndex+1):
        for j in range(1,len(source_list[i])-1):
            source_list[i][j] = source_list[i-1][j-1]+source_list[i-1][j]
    print(source_list)
    return source_list[-1]

print("买卖股票的最佳时机")
def maxProfit(prices:list[int]):
    min_price=prices[0]
    profit=0
    for p in prices[1::]:
        min_price = min(min_price,p)
        profit = max(profit,p-min_price)
    return profit


print("验证回文串")
def isHuiWenChuan(s:str) ->bool:
    temp=[]
    for ss in s:
        if ss.isdigit():
            temp.append(ss)
        if ss.isalpha():
            temp.append(ss.lower())
    target_str="".join(temp)
    return target_str == target_str[::-1]

print("给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素")
def singleNumber(nums:list[int])->int:
    for n in nums:
        if nums.count(n) == 1:
            return n

print("相交链表"
      "给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。")
class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
def getIntersectionNode(headA:ListNode,headB:ListNode)->ListNode:
    if headA is None or headB is None:
        return None
    # 遍历链表A，取出所有元素放入列表
    current= headA
    tem_list=[]
    while current:
        tem_list.append(current)
        current=current.next
    # 遍历链表B，看链表B中的元素是否在列表中，在的话就返回该相交节点，不存在返回none
    current = headB
    while current:
        if current in tem_list:
            return current
        current=current.next
    return None


print("给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称")
def convertToTitle(columnNumber:int) ->str:
    res =[]
    while columnNumber>0:
        columnNumber=columnNumber-1
        res.append(chr(columnNumber%26+ord("A")))
        columnNumber=columnNumber//26
    return "".join(res[::-1])


print("给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素")
def majorElement(nums:list[int]) -> int:
    for n in nums:
        if nums.count(n) > len(nums)/2:
            return n


print("给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回 该列名称对应的列序号")
def titleToNumber(columnTitle:str) ->int:
    res=0
    for column in columnTitle:
        # 每遍历一次，就会有n次满26的循环
        res=res*26+(ord(column)-64)
    return res

print("编写一个算法来判断一个数 n 是不是快乐数")
def isHappy(n:int)->bool:
    s=0
    tem_list=[]
    while True:
        for i in str(n):
            s=s+int(i)**2
        n=s
        s=0
        if n ==1:
            return True
        if n in tem_list:
            return False
        tem_list.append(n)

print("给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点")
class ListNode:
    def __init__(self,val,next=None):
        self.val=val
        self.next=next
def removeElements(head:ListNode,val:int)->ListNode:
    if head is None:
        return None
    new_head=ListNode()
    new_head.next=head
    current=new_head
    while current.next:
        if current.next.val==val:
            current.next=current.next.next
        else:
            current=current.next
    return new_head.next

print("反转链表")
class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
def reverseList(head:TreeNode)->ListNode:
    if head is None:
        return head
    pre=None
    current=head
    while current:
        temp=current.next
        current.next=pre
        pre=current
        current=temp
    return pre


print("判断是否存在重复元素")
def containDuplicate(self,nums):
    return not len(set(nums)) == len(nums)

print("判断是不是回文链表")
class ListNode:
    def __init__(self,val=0,next=None):
        self.val=val
        self.next=next
def isHuiwenLianBiao(head:ListNode)->bool:
    if head is None:
        return False
    res=[]
    current=head
    while current:
        res.append(current.val)
        current=current.next
    return res==res[::-1]


print("给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数")
def missingNumber(nums:list[int]) ->int:
    for i in range(0,len(nums)+1):
        if i not in nums:
            return i

print("给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序")
def moveZeroes(nums:list):
    count = nums.count(0)
    for i in range(0,count):
        nums.remove(0)
        nums.append(0)


print("给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false")
def isPowerOfThree(n:int)->bool:
    if n==1:
        return True
    if n==2:
        return False
    target=1
    while True:
        target=target*3
        if target ==n:
            return True
        elif target>n:
            return False


print("不使用切片反转字符串")
def reverseString(s:list[str]):
    for i in range(0,len(s)//2):
        temp=s[i]
        s[i]=s[len(s)-1-i]
        s[len(s)-1-i] = temp


print("给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，"
      "应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。")
def intersect(nums1:list,nums2:list)->list[int]:
    import collections
    return list((collections.Counter(nums1))&(collections.Counter(nums2)).elements())


print("给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1")
def firstUniquChar(s:str)->int:
    for i in range(0,len(s)):
        if s.count(s[i])==1:
            return i
    return -1

print("给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果")
# def addDigits(num:int) ->int:
#     res = 0
#     while True:
#         for i in str(num):
#             res = int(i)+res
#         if res//10 == 0:
#             return res
#         num = res
# print(10//10)

def addDigits(num:int)->int:
    while num>=10:
        a = num//10
        b= num%10
        num =a+b
    return num















































